# 给定一个二叉树，找出其最小深度。
# 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。x
# 说明：叶子节点是指没有子节点的节点。
#
#  示例：
# 给定二叉树 [3,9,20,null,null,15,7]，
#
#     3
#    / \
#   9  20
#     /  \
#    15   7
#
#  返回它的最小深度 2 。
import collections

from com.example.tree.tree_node import TreeNode
from typing import Optional


class Solution:
    def minDepth2(self, root: Optional[TreeNode]) -> int:
        """
        层序遍历(bfs)
        遍历整棵树。当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
        :param root:
        :return:
        """
        if not root:
            return 0
        queue = collections.deque([(root, 1)])
        while queue:
            tmpNode, tmpDepth = queue.popleft()
            if tmpNode.left is None and tmpNode.right is None:  # 当前节点为叶节点
                return tmpDepth
            if tmpNode.left:
                queue.append((tmpNode.left, tmpDepth + 1))
            if tmpNode.right:
                queue.append((tmpNode.right, tmpDepth + 1))
        return 0

    def minDepth1(self, root: Optional[TreeNode]) -> int:
        """
        dfs(后序遍历)
        :param root:
        :return:
        """
        if not root:  # 递归基：空树的深度为0
            return 0
        if not root.left and not root.right:  # 递归终止条件：当前节点为叶节点
            return 1
        leftMinDepth = self.minDepth1(root.left)  # 求出左子树的最小深度
        rightMinDepth = self.minDepth1(root.right)  # 求出右子树的最小深度
        if not root.left or not root.right:  # 当前节点左右子节点有一个为空（为空的节点的深度必为 0），则其最小深度为左右子树深度的较大值+1
            return max(leftMinDepth, rightMinDepth) + 1
        return min(leftMinDepth, rightMinDepth) + 1  # 当前节点左右子节点都不为空，则其最小深度为左右子树深度的较小值+1

    def minDepth(self, root: Optional[TreeNode]) -> int:
        return self.minDepth1(root)


if __name__ == "__main__":
    root = TreeNode(3)
    root.left, root.right = TreeNode(3), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print(Solution().maxDepth(root))
